#include "graph_support/TestGraphDecorators.h"

#include <vector>
#include <sstream>
#include <ext/hash_map>
namespace stdext
{
	using namespace __gnu_cxx;
}

#include <boost/pool/object_pool.hpp>

#include "graph_support/IGraph.h"

#include "graph_support/utils/test_my_graph/BoostTestUtils.h"

#include "graph_support/attributes/LengthEdgeAttributes.h"
#include "graph_support/attributes/FlowEdgeAttributes.h"
#include "graph_support/impls/vector/VectorGraph.h"
#include "graph_support/impls/matrix/MatrixGraph.h"
#include "graph_support/impls/compact/CompactGraph.h"
#include "graph_support/alg/shortest_path/Dejkstra.h"
#include "graph_support/alg/flow/Dinic.h"
#include "graph_support/decorate/JoinGraph.h"
#include "graph_support/decorate/ConvertGraphAttributes.h"

#include "graph_support/utils/CollectionsInit.h"
#include "graph_support/utils/GraphTemplateUtils.h"


using namespace GRAPH_SUPPORT_NS;
using namespace GRAPH_SUPPORT_NS::impls::vector;
using namespace GRAPH_SUPPORT_NS::impls::matrix;
using namespace GRAPH_SUPPORT_NS::impls::compact;
using namespace GRAPH_SUPPORT_NS::decorate;
using namespace GRAPH_SUPPORT_NS::alg::shortest_path;
using namespace GRAPH_SUPPORT_NS::alg::flow;
using namespace GRAPH_SUPPORT_NS::utils;

typedef VectorGraphTmpl< int > VGraph;
typedef MatrixGraphTmpl< int > MGraph;
typedef CompactGraphTmpl< int > CGraph;
typedef JoinGraphTmpl< VGraph, MGraph > JVMGraph;
typedef JoinGraphTmpl< VGraph, JoinGraphTmpl< MGraph, CGraph > > JVMCGraph;

/**
 * flow graph definitions
 */
namespace F
{

typedef attributes::FlowEdgeAttributesTmpl< double > FlowEdgeAttributes;
typedef VectorGraphTmpl< int, FlowEdgeAttributes > VGraph;

}

void TestJoinTwoGraphs()
{
	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3 } );

	VGraph vgr( vertices );
	MGraph mgr( vertices );

	vgr.addEdge( 0, 1 );
	mgr.addEdge( 1, 2 );

	JVMGraph jgr( vgr, mgr );

	BOOST_CHECK( findEdge( jgr, 0, 1 ) );
	BOOST_CHECK( findEdge( jgr, 1, 2 ) );
	{
	Dejkstra< JVMGraph > dejkstra( jgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 2.0, dejkstra.getDistance( 2 ), 1e-5 );
	}

	BOOST_CHECK( ! findEdge( jgr, 1, 3 ) );
	jgr.addEdge( 1, 3 );
	BOOST_CHECK( findEdge( jgr, 1, 3 ) );
	{
	std::stringstream buf;
	for ( JVMGraph::EdgeIterator eit = jgr.getEdgsBeg( 1 ); eit != jgr.getEdgsEnd( 1 ); ++eit )
	{
		buf << ( * eit )->beg() << " -> " << ( * eit )->end() << ", ";
	}
	BOOST_CHECK_EQUAL( "1 -> 3, 1 -> 2, ", buf.str() );
	}

	jgr.addEdge( 1, 0 );
	{
	std::stringstream buf;
	jgr.forEachOutEdge( 1,
			boost::bind( & shlOperator< std::stringstream, JVMGraph::GrVertex >, boost::ref( buf ),
					boost::bind( & JVMGraph::GrEdge::end,
							_1 ) )
	);
	BOOST_CHECK_EQUAL( "302", buf.str() );
	}

	JVMGraph::GraphPtr vgrPtr( new VGraph( vertices ) );
	JVMGraph::GraphPtr mgrPtr( new MGraph( vertices ) );
	JVMGraph jgr_storesAB( vgrPtr, mgrPtr );
	IGraph & vigr = dynamic_cast< IGraph & >( * vgrPtr );
	IGraph & migr = dynamic_cast< IGraph & >( * mgrPtr );
	IGraph::IEdgeAttributesPtr attributesSingletone(
			new IGraph::EdgeAttributesImpl< VGraph::EdgeAttributes >::CpAttributes(
					VGraph::EdgeAttributes() ) );
	vigr.iaddEdge( 0, 1, attributesSingletone );
	vigr.iaddEdge( 2, 3, attributesSingletone );
	{
	Dejkstra< JVMGraph > dejkstra( jgr_storesAB );
	dejkstra( 0 );
	BOOST_CHECK_GT( dejkstra.getDistance( 3 ), 1e5 );
	}
	migr.iaddEdge( 1, 2, attributesSingletone );
	{
	Dejkstra< JVMGraph > dejkstra( jgr_storesAB );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 3.0, dejkstra.getDistance( 3 ), 1e-5 );
	}
}

void TestJoinMultipleGraphs()
{
	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5, 6 } );

	JVMCGraph::GraphPtr vgrPtr( new VGraph( vertices ) );
	VGraph & vgr = dynamic_cast< VGraph & >( * vgrPtr );
	JVMCGraph::GraphPtr mgrPtr( new MGraph( vertices ) );
	MGraph & mgr = dynamic_cast< MGraph & >( * mgrPtr );
	JVMCGraph::GraphPtr cgrPtr( new CGraph( vertices ) );
	CGraph & cgr = dynamic_cast< CGraph & >( * cgrPtr );

	vgr.addEdge( 0, 1 );
	mgr.addEdge( 1, 2 );
	cgr.addEdge( 2, 3 );
	vgr.addEdge( 3, 4 );
	mgr.addEdge( 4, 5 );
	cgr.addEdge( 5, 6 );

	JVMCGraph jgr( vgrPtr, JVMCGraph::GraphPtr(
			new JoinGraphTmpl< MGraph, CGraph >( mgrPtr, cgrPtr ) ) );

	Dejkstra< JVMCGraph > dejkstra( jgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 6.0, dejkstra.getDistance( 6 ), 1e-5 );
}

namespace TestConvertAttributesDecorator_NS
{

typedef attributes::LengthEdgeAttributesTmpl< double > LengthEdgeAttributes;

LengthEdgeAttributes multiplyLength2( CGraph::GrEdgePtr & eptr )
{
	return LengthEdgeAttributes( 2 * eptr->getAttributes().getLength() );
}

LengthEdgeAttributes lengthIsCrazySum( CGraph::GrEdgePtr & eptr )
{
	return LengthEdgeAttributes(
			eptr->getAttributes().getLength() +
			eptr->begId() +
			eptr->endId() );
}

}

void TestConvertAttributesDecorator()
{
	using namespace TestConvertAttributesDecorator_NS;

	typedef ConvertGraphAttributesTmpl< CGraph, LengthEdgeAttributes > CnvAttrCGraph;
	typedef ConvertGraphAttributesTmpl< F::VGraph, attributes::Length1EdgeAttributes > CnvAttrFVGraph;

	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5, 6 } );

	CGraph gr( vertices );
	gr.addEdge( 0, 1 );
	gr.addEdge( 1, 2 );
	gr.addEdge( 2, 3 );

	{
	Dejkstra< CGraph > dejkstra( gr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 3.0, dejkstra.getDistance( 3 ), 1e-5 );
	}

	CnvAttrCGraph m2gr( gr, & multiplyLength2 );
	{
	Dejkstra< CnvAttrCGraph > dejkstra( m2gr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 6.0, dejkstra.getDistance( 3 ), 1e-5 );
	}

	CnvAttrCGraph csgr( gr, & lengthIsCrazySum );
	{
	Dejkstra< CnvAttrCGraph > dejkstra( csgr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 12.0, dejkstra.getDistance( 3 ), 1e-5 );
	}

	F::VGraph fvgr( vertices );
	fvgr.addEdge( 0, 1, 12 );
	fvgr.addEdge( 1, 2, 23 );
	fvgr.addEdge( 2, 3, 34 );
	CnvAttrFVGraph l1gr( fvgr, & convert_arguments_utils::lengthIs1< F::VGraph::GrEdgePtr > );
	{
	Dejkstra< CnvAttrFVGraph > dejkstra( l1gr );
	dejkstra( 0 );
	BOOST_CHECK_CLOSE( 3.0, dejkstra.getDistance( 3 ), 1e-5 );
	}
}

namespace TestConvertAttributesDecoratorOnStoreFlow_NS
{

typedef CompactGraphTmpl< int, attributes::LengthEdgeAttributesTmpl< double > > DLenCGraph;

class StoreFlowEdgeAttributes : public attributes::FlowEdgeAttributes
{
public:
	typedef F::FlowEdgeAttributes::Capacity Capacity;
public:
	StoreFlowEdgeAttributes( F::FlowEdgeAttributes * attributes )
		: attributes( attributes )
	{
	}
	StoreFlowEdgeAttributes( )
		: attributes( NULL )
	{
	}
	Capacity getCapacity()
	{
		return attributes->getCapacity();
	}
	void setCapacity( const Capacity & capacity )
	{
		attributes->setCapacity( capacity );
	}
	Capacity getFlow()
	{
		return attributes->getFlow();
	}
	Capacity getRemainCapacity()
	{
		return attributes->getRemainCapacity();
	}
	void addFlow( Capacity addFlow )
	{
		attributes->addFlow( addFlow );
	}
	void eraseFlow()
	{
		attributes->eraseFlow();
	}
	bool operator == ( const StoreFlowEdgeAttributes & that ) const
	{
		if ( this->attributes == NULL || that.attributes == NULL )
		{
			return this->attributes == that.attributes;
		} else
		{
			return ( * this->attributes ) == ( * that.attributes );
		}
	}
private:
	F::FlowEdgeAttributes * attributes;
};

template< typename T >
class PtrHash
{
public:
	size_t operator() ( T * ptr ) const
	{
		size_t result = reinterpret_cast< size_t >( ptr );
		return result;
		return reinterpret_cast< size_t >( ptr );
	}
	bool operator() ( T * ptrA, T * ptrB ) const
	{
		bool result = ptrA == ptrB;
		return result;
		return ptrA == ptrB;
	}
};

class LengthIsCapacity
{
public:
	LengthIsCapacity( DLenCGraph * gr = NULL )
		: gr( gr )
	{
	}
	LengthIsCapacity( const LengthIsCapacity & that )
		: gr( that.gr )
	{
	}
	StoreFlowEdgeAttributes operator () ( DLenCGraph::GrEdgePtr & eptr )
	{
		DLenCGraph::EdgeAttributes * origattrsPtr = & eptr->getAttributes();
		AttributesMap::iterator amiter = original2converted.find( origattrsPtr );
		if ( amiter != original2converted.end() )
		{
			return amiter->second;
		}
		F::FlowEdgeAttributes * attributes = attributesPool.construct( eptr->getAttributes().getLength() );
		F::FlowEdgeAttributes * rattributes = attributesPool.construct( eptr->getAttributes().getLength() );
		attributes->onBidirEdgeCreated( * rattributes, true );
		rattributes->onBidirEdgeCreated( * attributes, false );
		StoreFlowEdgeAttributes result( attributes );
		original2converted[origattrsPtr] = result;
		DLenCGraph::EdgeAttributes * rorigattrsPtr = findRevertedAttributes( eptr );
		if ( rorigattrsPtr != NULL )
		{
			original2converted[findRevertedAttributes( eptr )] = StoreFlowEdgeAttributes( rattributes );
		}
		assert( original2converted.find( origattrsPtr ) != original2converted.end() );
		return result;
	}
private:
	DLenCGraph::EdgeAttributes * findRevertedAttributes( DLenCGraph::GrEdgePtr & eptr )
	{
		if ( gr == NULL )
		{
			return NULL;
		}
		DLenCGraph::EdgeIterator stopeit = gr->getEdgsEndId( eptr->endId() );
		for ( DLenCGraph::EdgeIterator eit = gr->getEdgsBegId( eptr->endId() ); eit != stopeit; ++eit )
		{
			DLenCGraph::GrEdgePtr ceptr = * eit;
			if ( ceptr->begId() == eptr->endId() && ceptr->endId() == eptr->begId() )
			{
				return & ceptr->getAttributes();
			}
		}
		return NULL;
	}
private:
	typedef stdext::hash_map<
			DLenCGraph::EdgeAttributes *,
			StoreFlowEdgeAttributes,
			PtrHash< DLenCGraph::EdgeAttributes >
			> AttributesMap;
	DLenCGraph * gr;
	AttributesMap original2converted;
	boost::object_pool< F::FlowEdgeAttributes > attributesPool;
};

}

void TestConvertAttributesDecoratorOnStoreFlow()
{
	using namespace TestConvertAttributesDecoratorOnStoreFlow_NS;

	typedef DLenCGraph CGraph;
	typedef ConvertGraphAttributesTmpl< CGraph, StoreFlowEdgeAttributes, LengthIsCapacity > C2FGraph;

	std::vector< int > vertices = arr2vector< int >( ( const int [] ) { 0, 1, 2, 3, 4, 5, 6 } );

	CGraph gr( vertices, true );
	gr.addEdge( 0, 1, 123 );
	gr.addEdge( 0, 2, 12 );
	gr.addEdge( 2, 1, 23 );

	C2FGraph c2fgr( gr, LengthIsCapacity( & gr ) );
	/**
	 * initialises 2 -> 1 before 1 -> 2
	 */
	utils::findEdge( c2fgr, 2, 1 );
	BOOST_CHECK( utils::findEdge( c2fgr, 0, 1 ) );
	BOOST_CHECK_CLOSE( 123.0, utils::findEdge( c2fgr, 0, 1 ).get()->getAttributes().getCapacity(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, utils::findEdge( c2fgr, 0, 1 ).get()->getAttributes().getFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( 0.0, utils::findEdge( c2fgr, 1, 0 ).get()->getAttributes().getFlow(), 1e-5 );
	utils::findEdge( c2fgr, 0, 1 ).get()->getAttributes().addFlow( 1.0 );
	BOOST_CHECK_CLOSE( 1.0, utils::findEdge( c2fgr, 0, 1 ).get()->getAttributes().getFlow(), 1e-5 );
	BOOST_CHECK_CLOSE( -1.0, utils::findEdge( c2fgr, 1, 0 ).get()->getAttributes().getFlow(), 1e-5 );

	std::vector< C2FGraph::GrEdgePtr > buf;
	utils::findEdges( c2fgr, 0, 2, buf );
	BOOST_CHECK_EQUAL( 1, buf.size() );

	Dinic< C2FGraph > dinic( c2fgr );
	dinic( 0, 1 );
	BOOST_CHECK_CLOSE( 135.0, dinic.getTotalFlow(), 1e-5 );
}
